#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。



 

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：

输入：digits = ""
输出：[]
示例 3：

输入：digits = "2"
输出：["a","b","c"]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

//const char mapArr[] = {' ', ' ', 'a', 'd', 'g', 'j', 'm', 'p', 't', 'w'};
//vector<string> ret;
//
//static void backit(string digits, string temp, int nowIndex) {
//    //这次的出口怎么变成这个了 似乎也行
//    if (nowIndex >= digits.size()) {
//        ret.push_back(temp);
//        return;
//    }
//
//
//
//    //出口
//    if (temp.size() == digits.size()) {
//        ret.push_back(temp);
//        return;
//    }
//
//
//
//    //1  a
//
//
//    int now = digits[nowIndex] - '0';
//    int count = 3;
//    if (now == 9 || now == 7)count++;
//    for (int i = 0; i < count; ++i) {
//        temp.push_back(mapArr[now] + i);
//        backit(digits, temp, nowIndex + 1);
//        //回退
//        temp.pop_back();
//    }
//
//
//}
//
//static vector<string> letterCombinations(string digits) {
//
//    string temp = "";
//    backit(digits, temp, 0);
//    return ret;
//
//}


const char arrs[10] = {' ', ' ', 'a', 'd', 'g', 'j', 'm', 'p', 't', 'w'};
vector<string> ans;
string temp;

//index 表示字符串下标
void dfs(string &digits, int index, string temp) {
    if (digits.size() == temp.size()) {
        ans.push_back(temp);
        return;
    }
    if (digits.size() < temp.size() || index >= digits.size())
        return;


    char t = digits[index];
    int count = 3;
    if (digits[index] == '9' || digits[index] == '7')
        count++;

    for (int i = 0; i < count; i++) {
        char tp = arrs[t - '0'] + i;
        dfs(digits, index + 1, temp + tp);

    }


}

vector<string> letterCombinations(string digits) {
    dfs(digits, 0, "");
    return ans;

}